package com.jinan.algorithm.LinkList;

import com.jinan.common.ListNode;
import com.jinan.common.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;

public class ReverseList {

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5,null);
        ListNode node4 = new ListNode(4,node5);
        ListNode node3 = new ListNode(3,node4);
        ListNode node2 = new ListNode(2,node3);
        ListNode node1 = new ListNode(1,node2);

    }
    //链表反转
    //迭代
    public static ListNode reverseList(ListNode head)
    {
        ListNode pre = null,next;
        ListNode cur = head;
        while (cur != null)
        {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    //递归
    public static ListNode reverseList2(ListNode head)
    {
        if (head == null || head.next == null)
        {
            return head;
        }
        ListNode rest = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return rest;
    }

    /**
     * 92. 反转链表 II <a href="https://leetcode.cn/problems/reverse-linked-list-ii/solution/you-xie-cuo-liao-yi-ge-shi-pin-jiang-tou-teqq/">...</a>
     * 难度：中等
     * tag: 链表
     * description:
     * 给你单链表的头指针 head 和两个整数left 和 right ，其中left <= right 。
     * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     * @param head 链表头
     * @param left 链表反转的起始位置
     * @param right 链表反转的结束位置
     * @return ListNode 反转后的链表
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p0 = dummy;
        for(int i = 0; i < left - 1; i++){
            p0 = p0.next;
        }
        ListNode cur = p0.next;
        ListNode pre = null;
        for(int i = 0; i < right - left + 1; i++){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        p0.next.next = cur;
        p0.next = pre;
        return dummy.next;
    }
    /**
     * 25. K 个一组翻转链表 <a href="https://leetcode.cn/problems/reverse-nodes-in-k-group/solution/tu-jie-kge-yi-zu-fan-zhuan-lian-biao-by-user74/">...</a>
     * 难度：困难
     * tag: 链表
     * description:
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     * k 是一个正整数，它的值小于或等于链表的长度
     * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     * @param head 链表头
     * @param k 翻转的组数
     * @return ListNode 翻转后的链表
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1, head),p0=dummy;
        while(p0.next != null){
            ListNode p1 = p0;
            for(int i = 0; i < k; i++){
                p1 = p1.next;
                if(p1 == null) return dummy.next;
            }
            ListNode cur = p0.next;
            ListNode pre = null;
            for (int i = 0; i < k; i++){
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            ListNode next = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = next;
        }
        return dummy.next;
    }
    /**
     * 回文链表 <a href="https://leetcode.cn/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/">...</a>
     * 难度：简单
     * tag: 链表
     * description:
     * 请判断一个链表是否为回文链表。
     * restrictions:
     * 链表长度在 [1, 10^5]范围内。
     * 0 <= Node.val <= 9
     * @param head 链表头
     * @return boolean 是否为回文链表
     */
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        for (int i = 0, j = list.size() - 1; i < j; i++, j--) {
            if (!list.get(i).equals(list.get(j))) {
                return false;
            }
        }
        return true;
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    /**
     * 138.随机链表的复制 <a href="https://leetcode.cn/problems/copy-list-with-random-pointer/solution/fu-zhi-dai-sui-ji-zhi-zhen-de-lian-biao-by-leetcod/">...</a>
     * 难度：中等
     * tag: 链表
     * description:
     * 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
     * 要求返回这个链表的深拷贝。
     * restrictions:
     * 节点数目不超过 1000
     * -10^4 <= Node.val <= 10^4
     * Node.random为空（null）或指向链表中的节点。
     * @param head 链表头
     * @return Node 链表头
     * @apiNote 思路：
     * 1. 遍历链表，将每个节点的next指向下一个节点，random指向下一个节点的random节点
     * 2. 将链表拆分为两个链表，奇数链表为原链表，偶数链表为原链表random节点
     * 3. 将奇数链表和偶数链表合并
     * 4. 将奇数链表和偶数链
     */
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    /**
     * 109. 有序链表转换二叉搜索树
     * 难度：中等
     * tag: 链表
     * description:
     * 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
     * 本题中，一个高度平衡二叉搜索树定义为：
     * 一个高度平衡二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
     * @param head 链表头结点
     * @return TreeNode 二叉搜索树的头结点
     */
    public TreeNode<Integer> sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        } else if (head.next == null) {
            return new TreeNode<>(head.val);
        }

        // 找到链表中点
        ListNode mid = middleNode(head);
        // 找到中点的前一个节点
        ListNode premid = head;
        while (premid.next != mid) {
            premid = premid.next;
        }
        // 断开左子链表
        premid.next = null;
        // 断开右子链表
        ListNode right = mid.next;
        mid.next = null;

        // 创建根节点
        TreeNode<Integer> root = new TreeNode<>(mid.val);
        // 递归构建左子树
        root.left = sortedListToBST(head);
        // 递归构建右子树
        root.right = sortedListToBST(right);

        // 返回根节点
        return root;
    }

    /**
     * 找到链表的中间结点
     * @param head 链表头结点
     * @return ListNode 中间结点
     */
    private ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 108. 将有序数组转换为二叉搜索树
     * 难度：简单
     * tag: 链表
     * description:
     * 给定一个整数数组 nums ，其中 nums[i] 在区间 [0, 99] 内
     * 请你输出一个数组 answer ，其中 answer[i] 是 nums 中第 i 小的元素。
     * restrictions:
     * 1 <= nums.length <= 100
     * 0 <= nums[i] <= 99
     * @param nums 有序数组
     * @return TreeNode 二叉搜索树的头结点
     */
    public TreeNode<Integer> sortedArrayToBST(int[] nums) {
        return sortedArrayToBSTdfs(nums, 0, nums.length - 1);
    }

    private TreeNode<Integer> sortedArrayToBSTdfs(int[] nums, int left, int right) {
        if(left > right){
            return null;
        }
        int mid = (left + right) >>> 1;
        TreeNode<Integer> root = new TreeNode<>(nums[mid]);
        root.left = sortedArrayToBSTdfs(nums, left, mid - 1);
        root.right = sortedArrayToBSTdfs(nums, mid + 1, right);
        return root;
    }

}
